package main.leetcode.offer.firstround.from51to68;

import java.util.Arrays;

/**
 * 57.和为s的两个数字
 *
 * <p>输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
 *
 * <p>
 *
 * <p>示例 1：输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]
 *
 * <p>示例 2：输入：nums = [10,26,30,31,47,60], target = 40 输出：[10,30] 或者 [30,10]
 *
 * <p>限制：1 <= nums.length <= 10^5 1 <= nums[i] <= 10^6
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex57 {
    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(new ex57().twoSum(new int[] {10, 26, 30, 31, 47, 60}, 40)));
    }

    // 暴力
    //    public int[] twoSum(int[] nums, int target) {
    //        int cur;
    //        for (int i = 0; i < nums.length; i++) {
    //            cur = target - nums[i];
    //            for (int j = i + 1; j < nums.length; j++) {
    //                if (cur == nums[j]) return new int[] {nums[i], nums[j]};
    //                if (cur < nums[i]) break;
    //            }
    //        }
    //        return new int[] {};
    //    }

    // 双指针
    public int[] twoSum(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, sum;
        while (lo < hi) {
            sum = nums[lo] + nums[hi];
            if (sum < target) ++lo;
            else if (sum > target) --hi;
            else return new int[] {nums[lo], nums[hi]};
        }
        return new int[] {};
    }
}
